package package4;

import java.awt.Graphics;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JButton;
import javax.swing.JFrame;

/*
 * 用于显示一次随机产生的100个数据的排序结果与N次NUM个数据的7种单关键字排序结果的关键字最坏比较次数、最坏移动次数、平均比较次数和平均移动次数
 */

public class TheSortProgram extends JFrame implements ActionListener{
	
	private static final int HEIGHT = 800;				//窗口高
	private static final int WIDTH = 700;				//窗口宽
	private static final int SPACING = 100;				//窗口与格子空隙
	private static final int INTERVAL = 50;				//格子空隙
	private static final int NSORT= 100;				//NSORT次排序
	private static final int NUM = 100;					//NUM个数据
	private static final int RANGE = 150;				//产生随机数的范围0-RANGE
	
	private static int[] array1 = new int[NUM+1];		//用于产生NUM个随机数据，0号单元未用
	private static int[] array2 = new int[101];			//用于显示100个数据排序结果
	
	private static int[][] compareCount = new int[7][NSORT+1];		//存储7种排序结果的每次比较次数
	private static int[][] moveCount = new int[7][NSORT+1];			//存储7种排序结果的每次移动次数
	
	public void paint(Graphics g) {
		super.paint(g); 							//调用父类的paint()让每次画之前窗口擦干净
		
		for(int i = 0;i<10;i++) 					//画格子
			for(int j = 0;j<10;++j)
				g.drawRect(SPACING+i*INTERVAL,SPACING+j*INTERVAL,INTERVAL,INTERVAL);
		
		for(int i = 0;i<10;i++) 					//画array2数组数字
			for(int j = 0;j<10;++j)		
				g.drawString(String.valueOf(array2[i*10+j+1]), SPACING+j*INTERVAL+INTERVAL/2-10, SPACING+i*INTERVAL+INTERVAL/2+5);
	
		//******画字横*****
		g.drawString("最坏比较次数",SPACING , HEIGHT-160);
		g.drawString("最坏移动次数",SPACING+2*INTERVAL, HEIGHT-160);
		g.drawString("平均比较次数",SPACING+4*INTERVAL, HEIGHT-160);
		g.drawString("平均移动次数",SPACING+6*INTERVAL, HEIGHT-160);
		//******画字竖*****
		g.drawString("直接插入排序",10, HEIGHT-140);
		g.drawString("希尔排序",10, HEIGHT-120);
		g.drawString("冒泡排序",10, HEIGHT-100);
		g.drawString("快速排序",10, HEIGHT-80);
		g.drawString("简单选择排序",10, HEIGHT-60);
		g.drawString("堆排序",10, HEIGHT-40);
		g.drawString("2路归并排序",10, HEIGHT-20);
		
		/***************************************************************
		 * 画各排序最坏比较次数、最坏移动次数、平均比较次数和平均移动次数,函数avg在后面，其作用为求一
		 * 个数组的平均值，compareCount[i][100]，moveCount[i][100]为排序后的最大元素
		 ***************************************************************/
		for(int i = 0;i<7;++i) {
			g.drawString(""+compareCount[i][100], SPACING+10, HEIGHT-200+20*(i+3)); 
			g.drawString(""+moveCount[i][100],SPACING+10+2*INTERVAL, HEIGHT-200+20*(i+3));
			g.drawString(""+avg(compareCount[i]),SPACING+10+4*INTERVAL, HEIGHT-200+20*(i+3));
			g.drawString(""+avg(moveCount[i]),SPACING+10+6*INTERVAL, HEIGHT-200+20*(i+3));
		}
		
	}
	
	public static void main(String[] arg) {
		
		for(int j = 1;j <= 100;++j) 					  //生成一个150内的100个元素的数组存在array2中
			array2[j] = (int)(Math.random()*150);
		
		//***************创建窗口***************
		theSortProgram win = new theSortProgram();			
		win.setSize(WIDTH,HEIGHT);
		win.setTitle("SORT");
		win.setLocationRelativeTo(null);
		win.setResizable(false);
		win.setDefaultCloseOperation(DISPOSE_ON_CLOSE);
		win.setVisible(true);
		
		//***************添加一个开始按钮**************
		JButton button = new JButton("start");
		button.setBounds(10, SPACING-30, SPACING-40, SPACING-40);
		button.addActionListener(win);
		win.add(button);
		
	}
	
	/*********************************************
	 ********************一、插入类******************
	 ********************************************/
	
	//**********0.直接插入排序**********
	//从第二个开始，若小于前一个元素，放入哨兵，前一个元素放在此元素位置，然后从前一个元素的前一个开始向前选择合适位置插入，边选择边向后移，0号单元作为哨兵位
	public void insertSort(int[] array,int n) {									//这个n表示第n次排序，下同
		 for(int i = 2;i < array.length;++i)
			 if( (++compareCount[0][n])!=0&&array[i] < array[i-1]) {			//根据&&计算的机制，把++comparecount放在前面，后面同
				 array[0] = array[i];											//该元素小于前一元素，放入哨兵
				 array[i] = array[i-1];
				 moveCount[0][n] += 2;											//交换元素为移动元素
				 int j;
				 for(j = i-2;(++compareCount[0][n])!=0&&j>0&&array[0] < array[j];--j) {
					 array[j+1] = array[j];										//边选择边后移
					 moveCount[0][n]++;
				 }
				 array[j+1] = array[0];											//合适位置插入之前放入哨兵的元素
				 moveCount[0][n]++;
			 }
	}
	
	//**********1.希尔排序**********
	//希尔排序为按步长的直接插入排序，确定步长后其他同直接插入排序
	public void shellSort(int[] array,int n) {	
		//取步长为2^(t-k+1)-1， 0 <= k <= t <= log2(n+1)取下整,一次递减最后一次为1，步长只要符合要求就行了，最好他们之间无除1以外的公因子
		int t = (int)(Math.log10(n+1)/Math.log10(2));
		for(int k = 0 ; k <= t;++k) {
			int dk = 2^(t-k+1)-1;								//dk为步长					     
			for(int i = dk+1;i<array.length;++i) {			//直接插入排序的dk为1,所以加dk就行了
				if((++compareCount[1][n])!=0&&array[i] < array[i-dk]) {
					array[0] = array[i];
					array[i] = array[i-dk];
					moveCount[1][n]+=2;
					int j;
					for(j = i-2*dk;(++compareCount[1][n])!=0&&j>0&&array[0]<array[j];j-=dk) {
						array[j+dk] = array[j];
						moveCount[1][n]++;
					}
					array[j+dk] = array[0];
					moveCount[1][n]++;
				}
			}
		}
	}
	
	/*********************************************
	 ********************二、交换类******************
	 ********************************************/
	
	//**********2.冒泡排序**********
	//像泡泡一样，比较紧挨两个，小的往前走。
	public void bubbleSort(int[] array,int n) {			
		for(int i = array.length;i>0;--i) {
			int flag = 0;						//设立flag，当有交换时为1，无交换时为0，为0时说明已经排好了，直接结束
			for(int j = 1;j<i;++j) 
				if((++compareCount[2][n])!=0&&array[j-1]>array[j]) {		//小的往前
					int temp = array[j-1];
					array[j-1] = array[j];
					array[j] = temp;
					flag = 1;					//有交换flag=1
					moveCount[2][n]+=3;
				}
			if(flag == 0)
				break;
		}
	}
	
	//**********3.快速排序**********
	//快速排序需要先确定中枢，一般先取第一个、最后一个和中间一个的中间值，然后将其与第一个交换，将其放在哨兵，再进行循环从high往前把比中枢元素小的第一个元素放在之前放在了哨兵元素的low
	//然后，循环从low开始往后选择第一个大于中枢的放在刚才的放到low位置的那个位置，这样就不会出现覆盖了，每次只能使中枢前面的小于中枢后面的，总体有序，于是还需区间分小，可用递归减半区间。
	public int partition(int[] array,int low,int high,int n) {
		//取low,high,和(low+high)/2中间的那个为中枢，本人用的方法较笨
		int pivot ;
		int[] temp =new int[] {array[low],array[(low+high)/2],array[high]};
		for(int i = 0;i<2;++i)				//先排序
			if(temp[i]>temp[i+1]) {
				int t = temp[i];
				temp[i] = temp[i+1];
				temp[i+1] = t;
				moveCount[3][n]+=3;
			}
		if(temp[1]==array[low])				//再选择中间的为中枢位置
			pivot = low;
		else if(temp[1]==array[high])
			pivot = high;
		else
			pivot = (low+high)/2;
		if(pivot!=low) {			        //把中枢与array[low]交换，选择其他为中枢时，只需把其与low交换就行，下面不变
			int t = array[pivot];
			array[pivot] = array[low];
			array[low] = t;
			moveCount[3][n]+=3;
		}
		
		array[0] = array[low];				//把low元素存在哨兵
		while(low<high) {
			while(low<high&&(++compareCount[3][n])!=0&&array[high]>=array[0])		//high往前选择第一个小于中枢的，放在low位置
				--high;
			array[low] = array[high];
			moveCount[3][n]++;
			while(low<high&&(++compareCount[3][n])!=0&&array[low]<=array[0])		//low往后选择第一个大于中枢的，放在刚才空出位置
				++low;
			array[high] = array[low];
			moveCount[3][n]++;
		}
		array[low] = array[0];				//最后把哨兵放在中枢位置
		moveCount[3][n]++;
		return low;							//返回中枢位置
	}
	
	//递归“减半”进行快速排序
	public void qSort(int[] array,int low,int high,int n) {
		if(low<high) {
			int pivotloc = partition(array,low, high,n);		//求出中枢位置，顺便进行一次快速排序
			qSort(array,low, pivotloc - 1,n);			
			qSort(array,pivotloc+1, high,n);
		}
	}
	
	//快速排序
	public void quickSort(int[] array,int n) {			
		qSort(array,1, array.length-1,n);
	}
	
	
	/*********************************************
	 ********************三、选择类******************
	 ********************************************/
	
	//**********4.简单选择排序**********
	//选择最小的元素，然后把与第一个元素交换。为了不让全局变量发生变化，展示排序结果，重载了一个简单选择排序函数，也可以选择其他的排序函数就进行重载
	public void selectSort(int[] array) {			
		for(int i = 1;i<array.length;++i) {
			int min = i;					//先第一个为最小
			for(int j = i+1;j<array.length;++j)
				if(array[min]>array[j])		//找到最小
					min = j;
			if(min!=i) {					//进行交换
				int temp = array[min];
				array[min] = array[i];
				array[i] = temp;
			}
 		}
	}
	public void selectSort(int[] array,int n) {			
		for(int i = 1;i<array.length;++i) {
			int min = i;
			for(int j = i+1;j<array.length;++j)
				if((++compareCount[4][n])!=0&&array[min]>array[j])
					min = j;
			if(min!=i) {
				int temp = array[min];
				array[min] = array[i];
				array[i] = temp;
				moveCount[4][n]+=3;
			}
 		}
	}
	
	//**********5.堆排序**********
	//堆调整，将其调整为大顶堆
	public void heapAdjust(int[] array,int s,int m,int n) {	      
		//数组中s-m除s外均满足堆定义，本函数使s-m成为一个大顶堆
		int rc = array[s];					//先把s位置存下来		
		moveCount[5][n]++;
		for(int j = 2*s;j<=m;j*=2) {		//沿值较大的节点向下筛选
			if(j<m&&(++compareCount[5][n])!=0&&array[j]<array[j+1])		
				++j;						//比较之后让j成为较大的下标
			if((++compareCount[5][n])!=0&&rc>=array[j])		//rc找到插入位置
				break;
			array[s] = array[j];			
			moveCount[5][n]++;
			s = j;
		}
		array[s] = rc;						//插入
		moveCount[5][n]++;
	}
	//堆排序
	public void heapSort(int[] array,int n) {			             
		for(int i = (array.length-1)/2;i>0;--i) {
			heapAdjust(array,i,array.length-1,n);		//把数组1-length建成大顶堆
		}
		
		for(int i = array.length-1;i>1;--i) {
			int temp =array[1];
			array[1] = array[i];						//将堆顶记录和当前为排序的1-i中最后一个记录相互交换
			array[i] = temp;
			moveCount[5][n]+=3;
			
			heapAdjust(array,1, i-1,n);					//将1-i-1重新调整为大顶堆
		}
	}
	
	/*********************************************
	 ********************四、归并类*********************
	 ********************************************/
	
	//**********6.2-路归并排序**********
	//二路归并主要为有序表的合并，从单个元素合并为两个有序，两个变为四个有序，最后有序，可用递归实现
	//有序表合并
	public void merge(int[] array,int s,int m,int t,int n) {	//s为第一个表的首位置，m为表尾，m+1为第二个表的首位置，t为表尾			
		int i = s,j = m+1,k = 0;
		int[] p = new int[t-s+1];			//创建一个新表存放合并表，也可直接存在表一
		while(i<=m&&j<=t) {
			if((++compareCount[6][n])!=0&&array[i]<=array[j]) {
				p[k++] = array[i++];		//两个表都没结束，小的先放
				moveCount[6][n]++;
			}
			else {
				p[k++] = array[j++];
				moveCount[6][n]++;
			}
		}
		while(i<=m) {						//将剩余的表一放在新表
			p[k++] = array[i++];
			moveCount[6][n]++;
		}
		while(j<=t) {						//将剩余的表二放在新表
			p[k++] = array[j++];
			moveCount[6][n]++;
		}
		for(k = 0;k<=t-s;k++) {				//将新表覆盖原来数组那一段
			array[s+k] = p[k];
			moveCount[6][n]++;
		}
	}
	//递归归并排序，递归二路归并排序，然后合并
	public void mSort(int[] array,int s,int t,int n) {			        
		if(s<t) {
			int m = (s+t)/2;
			mSort(array,s, m,n);
			mSort(array,m+1, t,n);
			merge(array,s,m,t,n);
		}
		
	}
	//归并排序
	public void mergingSort(int[] array,int n) {			            
		mSort(array,1, array.length-1,n);
	}
	
	@Override
	public void actionPerformed(ActionEvent e) {
		
			selectSort(array2);			 //排序了array2用于展示排序结果，也可用其他排序
			
		for(int i = 1;i<=NSORT;++i) {	//复制了数组array1进行各种排序，然后得关键字最坏比较次数、最坏移动次数、平均比较次数和平均移动次数
			for(int j = 1;j <= NUM;++j) //每次排序之后又随机一组数据
				array1[j] = (int)(Math.random()*RANGE);
			int[] array= array1.clone();
			insertSort(array,i);
			array = array1.clone();
			shellSort(array,i);
			array = array1.clone();
			bubbleSort(array,i);
			array = array1.clone();
			quickSort(array,i);
			array = array1.clone();
			selectSort(array,i);
			array = array1.clone();
			heapSort(array,i);
			array = array1.clone();
			mergingSort(array,i);
		}
		
		for(int i=0;i<7;++i) {
			selectSort(compareCount[i]);		//对compareCount和moveCount进行排序，用于获得关键字最坏比较次数、最坏移动次数
			selectSort(moveCount[i]);
		}
		this.repaint();							//重画，得到结果
	}
	
	public int avg(int[] a) {					//计算数组的平均值
		int ave = 0;
		for(int i = 1;i<a.length;++i)
			ave += a[i];
		ave /= (a.length-1);
		return ave;
	}
}
